package daily.year2024.m11;

/**
 * No.316 去除重复字母
 *
 * @author wjs 2024/11/5
 */
public class d5 {
    class Solution {
        //1、为什么使用单调栈？
        //在一个字符串中，如果只删除一个字符，使得改变后的字符字典序最小，该怎么删除？
        //答案是删除下标i最小的满足s[i] > s[i+1]的元素。
        //基于以上的结论，可以使用单调栈维护最终的字符串，也就是在尽量保持递增的前提下保证所有的字符只出现一次
        public String removeDuplicateLetters(String s) {
            char[] chars = s.toCharArray();
            int n = chars.length;
            int[] remains = new int[26];
            boolean[] set = new boolean[26];
            int[] stack = new int[n];
            int l = 0;
            for(int i=0;i < n;i++) {
                int idx = chars[i] - 'a';
                remains[idx]++;
            }
            for(int i=0;i < n;i++) {
                int idx = chars[i] - 'a';
                while(l > 0 && !set[idx] && idx < stack[l-1] && remains[stack[l-1]] > 0) {
                    //出栈
                    set[stack[l-1]] = false;
                    l--;
                }
                if(!set[idx]) {
                    stack[l] = idx;
                    l++;
                    set[idx] = true;
                }
                remains[idx]--;
            }
            StringBuilder sb = new StringBuilder();
            for(int i=0;i < l;i++) {
                char tmp = (char)(stack[i] + 'a');
                sb.append(tmp);
            }
            return sb.toString();
        }
    }
}
